//========================================================================
/**
*  Copyright (c), 2007-2009.
*  @file	cx_list.h
*  @author	godwinguo
*  @email	godwinguo@tencent.com
*  @brief	Red-black search tree
*  @version	1.0.0
*  @history
*    <author>      <time>      <version>     <desc>
*  ------------ ------------  ------------  -----------------
*    godwinguo   2010/01/19     1.0.0        Create
*/
//========================================================================

#include "cx_rbtree.h"
#include "cx_typedef.h"
#include "cx_debug.h"
#include "cx_memory.h"

/*************************************************************************
* LOCAL FUNCTION
*************************************************************************/

static rb_node_ptr_t	__rb_rotate_left( rb_node_ptr_t root, rb_node_ptr_t node );
static rb_node_ptr_t	__rb_rotate_right( rb_node_ptr_t root, rb_node_ptr_t node );
static rb_node_ptr_t	__rb_erase_color( rb_node_ptr_t root, rb_node_ptr_t node, rb_node_ptr_t parent );

/*************************************************************************
* IMPLEMENTATION
*************************************************************************/

/*************************************************************************
* DESCRIPTION
*	$$__FUNC_DESC__$$
*************************************************************************/
rb_node_ptr_t cx_rb_allocNode( void )
{
	rb_node_ptr_t node;
	
	node = (rb_node_ptr_t)cx_malloc( sizeof(rb_node_t) );
	if ( NULL == node )
		return NULL;
	
	node->key		= NULL;
	node->val		= NULL;
	node->parent	= NULL;
	node->color		= RB_RED;
	node->left		= NULL;
	node->right		= NULL;

	return node;
}

/*************************************************************************
* DESCRIPTION
*	$$__FUNC_DESC__$$
*************************************************************************/
void rb_freeNode( rb_node_ptr_t node )
{
	cx_free( node );
}

/*************************************************************************
* DESCRIPTION
*	$$__FUNC_DESC__$$
*************************************************************************/
rb_node_ptr_t rb_insert( rb_node_ptr_t root, rb_node_ptr_t node )
{
	rb_node_ptr_t	temp;
	rb_node_ptr_t	uncle;
	rb_node_ptr_t	parent = NULL;
	rb_node_ptr_t	grand_parent;

	ASSERT( NULL != node );

	if ( NULL == root )
	{
		root = node;
		root->color = RB_BLACK;
		return root;
	}

	for ( ;; )
	{
		parent = node->parent;
		if ( NULL == parent || RB_RED != parent->color )
			break;

		grand_parent = parent->parent;
		if ( parent == grand_parent->left )
		{
			uncle = grand_parent->right;

			if ( NULL != uncle && RB_RED == uncle->color )
			{
				uncle->color		= RB_BLACK;
				parent->color		= RB_BLACK;
				grand_parent->color	= RB_RED;

				node = grand_parent;
				continue;
			}

			if ( parent->right == node )
			{
				root = __rb_rotate_left( root, parent );

				temp	= parent;
				parent	= node;
				node	= temp;
			}

			parent->color		= RB_BLACK;
			grand_parent->color	= RB_RED;
			
			root = __rb_rotate_right( root, grand_parent );
		}
		else
		{
			uncle = grand_parent->left;

			if ( NULL != uncle && RB_RED == uncle->color )
			{
				uncle->color		= RB_BLACK;
				parent->color		= RB_BLACK;
				grand_parent->color	= RB_RED;

				node = grand_parent;
				continue;
			}
			
			if ( parent->left == node )
			{
				root = __rb_rotate_right( root, parent );
				
				temp	= parent;
				parent	= node;
				node	= temp;
			}

			parent->color		= RB_BLACK;
			grand_parent->color	= RB_RED;

			root = __rb_rotate_left( root, grand_parent );
		}
	}

	root->color = RB_BLACK;

	return root;
}

/*************************************************************************
* DESCRIPTION
*	$$__FUNC_DESC__$$
*************************************************************************/
static rb_node_ptr_t __rb_erase_color( rb_node_ptr_t root, rb_node_ptr_t node, rb_node_ptr_t parent )
{
	rb_node_ptr_t	other;

	while ( (NULL == node || RB_BLACK == node->color) && (node != root) )
	{
		if ( parent->left == node )
		{
			other = parent->right;

			if ( RB_RED == other->color )
			{
				other->color	= RB_BLACK;
				parent->color	= RB_RED;

				root = __rb_rotate_left( root, parent );

				other = parent->right;
			}

			if ( NULL == other->left || RB_BLACK == other->left->color )
			{
				other->color = RB_RED;
				node = parent;
				parent = node->parent;
			}
			else if ( NULL == other->right || RB_BLACK == other->right->color )
			{
				other->color = RB_RED;
				node = parent;
				parent = node->parent;
			}
			else
			{
				if ( NULL == other->right || RB_BLACK == other->right->color )
				{
					other->left->color = RB_BLACK;
					other->color = RB_RED;

					root = __rb_rotate_right( root, other );
					other = parent->right;
				}

				other->color		= parent->color;
				parent->color		= RB_BLACK;
				other->right->color	= RB_BLACK;

				root = __rb_rotate_left( root, parent );

				node = root;
				break;
			}
		}
		else
		{
			other = parent->left;

			if ( RB_RED == other->color )
			{
				other->color	= RB_BLACK;
				parent->color	= RB_RED;

				root = __rb_rotate_right( root, parent );

				other = parent->left;
			}

			if ( NULL == other->left || RB_BLACK == other->left->color )
			{
				other->color = RB_RED;
				node = parent;
				parent = node->parent;
			}
			else if ( NULL == other->right || RB_BLACK == other->right->color )
			{
				other->color = RB_RED;
				node = parent;
				parent = node->parent;
			}
			else
			{
				if ( NULL == other->left || RB_BLACK == other->left->color )
				{
					other->right->color	= RB_BLACK;
					other->color		= RB_RED;

					root = __rb_rotate_left( root, other );

					other = parent->left;
				}

				other->color = parent->color;
				parent->color = RB_BLACK;
				other->left->color = RB_BLACK;

				root = __rb_rotate_right(parent, root);

				node = root;
				break;
			}
		}
	}

	if ( NULL != node )
	{
		node->color = RB_BLACK;
	}

	return root;
}

/*************************************************************************
* DESCRIPTION
*	$$__FUNC_DESC__$$
*************************************************************************/
static rb_node_ptr_t __rb_rotate_left( rb_node_ptr_t root, rb_node_ptr_t node )
{
	rb_node_ptr_t	right;
	rb_node_ptr_t	parent;

	ASSERT( NULL != root );
	ASSERT( NULL != node );

	right		= node->right;
	parent		= node->parent;

	node->right	= right->left;
	if ( NULL != node->right )
	{
		right->left->parent = node;
	}

	right->left		= node;
	right->parent	= parent;

	if ( NULL != parent )
	{
		if ( node == parent->left )
		{
			parent->left = right;
		}
		else
		{
			parent->right = right;
		}
	}
	else
	{
		root = right;
	}

	node->parent = right;

	return root;
}

/*************************************************************************
* DESCRIPTION
*	$$__FUNC_DESC__$$
*************************************************************************/
static rb_node_ptr_t __rb_rotate_right( rb_node_ptr_t root, rb_node_ptr_t node )
{
	rb_node_ptr_t	left;
	rb_node_ptr_t	parent;

	ASSERT( NULL != root );
	ASSERT( NULL != node );

	left		= node->left;
	parent		= node->parent;

	node->left	= left->right;
	if ( NULL != node->left )
	{
		left->right->parent = node;
	}

	left->right		= node;
	left->parent	= parent;

	if ( NULL != parent )
	{
		if (node == parent->right)
		{
			parent->right = left;
		}
		else
		{
			parent->left = left;
		}
	}
	else
	{
		root = left;
	}

	node->parent = left;

	return root;
}

/*************************************************************************
* DESCRIPTION
*	$$__FUNC_DESC__$$
*************************************************************************/
rb_node_ptr_t cx_rb_erase( rb_node_ptr_t root, rb_node_ptr_t node )
{
	rb_node_ptr_t	child;
	rb_node_ptr_t	parent;
	unsigned long	color;

	ASSERT( NULL != root );
	ASSERT( NULL != node );

	if ( NULL == node->left )
	{
		child = node->right;
	}
	else if ( NULL == node->right )
	{
		child = node->left;
	}
	else
	{
		rb_node_ptr_t	old = node;
//		rb_node_ptr_t	left;

		node = node->right;
		for ( ;; )
		{
			if ( NULL == node->left )
				break;
			node = node->left;
		}
		
		if ( NULL != old->parent )
		{
			if ( old->parent->left == old )
			{
				old->parent->left = node;
			}
			else
			{
				old->parent->right = node;
			}
		}
		else
		{
			root = node;
		}
		
		child	= node->right;
		parent	= node->parent;
		color	= node->color;
		
		if ( parent == old )
		{
			parent = node;
		}
		else
		{
			if ( NULL != child )
			{
				child->parent = parent;
			}

			parent->left	= child;
			node->right		= old->right;

			ASSERT( NULL != old->right );
			old->right->parent	= node;
		}

		node->color	= old->color;
		node->left	= old->left;

		ASSERT( NULL != old->left );
		old->left->parent = node;

		goto __COLOR;
	}
	
	parent	= node->parent;
	color	= node->color;
	
	if ( NULL != child )
	{
		child->parent = parent;
	}

	if ( NULL != parent )
	{
		if ( parent->left == node )
		{
			parent->left = child;
		}
		else
		{
			parent->right = child;
		}
	}
	else
	{
		root = child;
	}
	
__COLOR:

	if ( color == RB_BLACK )
	{
		root = __rb_erase_color( root, child, parent );
	}

	return root;
}

/*************************************************************************
* DESCRIPTION
*	$$__FUNC_DESC__$$
*************************************************************************/
rb_node_ptr_t cx_rb_replace( rb_node_ptr_t root, rb_node_ptr_t old_node, rb_node_ptr_t new_node )
{
	rb_node_ptr_t parent;

	ASSERT( NULL != root );
	ASSERT( NULL != old_node );
	ASSERT( NULL != new_node );

	parent = old_node->parent;

	if ( NULL != parent )
	{
		if ( old_node == parent->left )
		{
			parent->left = new_node;
		}
        else
		{
			parent->right = new_node;
		}
	}
	else
	{
		root = new_node;
	}

	if ( NULL != old_node->left )
	{
		old_node->left->parent = new_node;
	}

	if ( NULL != old_node->right )
	{
		old_node->right->parent = new_node;
	}

	new_node->color		= old_node->color;
	new_node->left		= old_node->left;
	new_node->right		= old_node->right;
	new_node->parent	= old_node->parent;

	return root;
}

/*************************************************************************
* DESCRIPTION
*	$$__FUNC_DESC__$$
*************************************************************************/
rb_node_ptr_t cx_rb_next( rb_node_ptr_t node )
{
	rb_node_ptr_t parent;

	if ( NULL == node )
		return NULL;

	if ( node->parent == node )
		return NULL;

	if ( NULL != node->right )
	{
		node = node->right;

		for ( ;; )
		{
			if ( NULL == node->left )
				break;

			node = node->left;
		}
		
		return node;
	}

	for ( ;; )
	{
		parent = node->parent;

		if ( NULL == parent )
			break;
		if ( node != parent->right )
			break;

		node = parent;
	}

	return parent;
}

/*************************************************************************
* DESCRIPTION
*	$$__FUNC_DESC__$$
*************************************************************************/
rb_node_ptr_t cx_rb_prev( rb_node_ptr_t node )
{
	rb_node_ptr_t parent;
	
	if ( NULL == node )
		return NULL;
	
	if ( node->parent == node )
		return NULL;
	
	if ( NULL != node->left )
	{
		node = node->left;
		
		for ( ;; )
		{
			if ( NULL == node->right )
				break;
			
			node = node->right;
		}
		
		return node;
	}
	
	for ( ;; )
	{
		parent = node->parent;
		
		if ( NULL == parent )
			break;
		if ( node != parent->left )
			break;
		
		node = parent;
	}
	
	return parent;
}

/*************************************************************************
* DESCRIPTION
*	$$__FUNC_DESC__$$
*************************************************************************/
rb_node_ptr_t cx_rb_first( rb_node_ptr_t root )
{
	rb_node_ptr_t	temp;

	if ( NULL == root )
		return NULL;

	temp = root;
	while ( NULL != temp->left )
	{
        temp = temp->left;
	}

	return temp;
}

/*************************************************************************
* DESCRIPTION
*	$$__FUNC_DESC__$$
*************************************************************************/
rb_node_ptr_t cx_rb_last( rb_node_ptr_t root )
{
	rb_node_ptr_t	temp;
	
	if ( NULL == root )
		return NULL;
	
	temp = root;
	while ( NULL != temp->right )
	{
        temp = temp->right;
	}
	
	return temp;
}

/*************************************************************************
* DESCRIPTION
*	$$__FUNC_DESC__$$
*************************************************************************/
rb_node_ptr_t cx_rb_search( rb_node_ptr_t root, cx_i2_fptr_t cmp_func, void * key,
								rb_node_ptr_t * pparent, rb_node_ptr_t ** pplink )
{
	register signed long	result;
	rb_node_ptr_t			parent = NULL;
	rb_node_ptr_t *			link = NULL;
	rb_node_ptr_t			node = root;
	
	for ( ; NULL != node; )
	{
		if ( NULL == cmp_func )
		{
			result = (signed long)key - (signed long)node->key;
		}
		else
		{
			result = cmp_func( key, (void *)node->key );
		}
		
		if ( result < 0 )
		{
			parent	= node;
			link	= &node->left;
			node	= node->left;
		}
		else if ( result > 0 )
		{
			parent	= node;
			link	= &node->right;
			node	= node->right;
		}
		else
		{
			parent	= NULL;
			link	= NULL;
			break;
		}
	}

	if ( NULL != pplink )
	{
		*pplink = link;
	}

	if ( NULL != pparent )
	{
		*pparent = parent;
	}

	return node;
}
